/*
 * Project: Sudoku Hint Engine for Android
 * Copyright (C) 2010-2013 Emanuel Moecklin
 * 
 * Available under the terms of the Lesser General Public License (LGPL)
 */
package com.onegravity.sudoku.solver.data;

import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;
import java.util.Vector;

/**
 * @author Emanuel Moecklin
 */
@SuppressWarnings("unchecked")
public class NeighborManager {

	/**
	 * Get neighbors for a specific cell.
	 * The method can deal with normal & jigsaw puzzles and works with extra regions
	 */
	public static int[] getNeighbors(Puzzle puzzle, int x, int y) {
		return getNeighbors(puzzle)[getPos(x, y)];
	}
	public static int[] getNeighbors(Puzzle puzzle, int index) {
		return getNeighbors(puzzle)[index];
	}

	/**
	 * Get neighbors for a puzzle.
	 * The method can deal with normal & jigsaw puzzles and works with extra regions
	 */
    public static int[][] getNeighbors(Puzzle puzzle) {
		if (puzzle.isJigsaw()) {
			byte[][] blockCodes = puzzle.getBlockCodes();
			if (puzzle.hasExtraRegions()) {
				// jigsaw puzzle with extra regions
				switch (puzzle.getExtraRegionType()) {
				case X: return neighbors_jigsaw_x(blockCodes);
				case HYPER: return neighbors_jigsaw_hyper(blockCodes);
				case PERCENT:  return neighbors_jigsaw_percent(blockCodes);
				case CENTERDOT: return neighbors_jigsaw_centerdot(blockCodes);
				case ASTERISK: return neighbors_jigsaw_asterisk(blockCodes);
				case COLOR: return neighbors_jigsaw_color(blockCodes);
				case NONE: break;
				}
			}
			// jigsaw puzzle without extra regions
			return neighbors_jigsaw_all(blockCodes);
		}
		else if (puzzle.hasExtraRegions()) {
			// normal puzzle with extra regions
			switch (puzzle.getExtraRegionType()) {
			case X: return neighbors_normal_x();
			case HYPER: return neighbors_normal_hyper();
			case PERCENT:  return neighbors_normal_percent();
			case CENTERDOT: return neighbors_normal_centerdot();
			case ASTERISK: return neighbors_normal_asterisk();
			case COLOR: return neighbors_normal_color();
			case NONE: break;
			}
		}
		// normal puzzle without extra regions
		return neighbors_normal_all();
	}

    // ****************************************** Static Initializer *******************************************

    /*
     * The static initializer computes the different elements needed to "assemble" neighbors for different puzzle types:
     * rows, columns, standard blocks, rows & columns, rows & columns & standard blocks,
     * x sudoku region, hyper sudoku region, percent region, centerdot region, asterisk region, color region (only the regions)
     * These lists (List<Set<Integer>>) are later converted into neighbor arrays for different puzzle types (int[][]) 
     */

    private static List<Set<Integer>> neighbors_row = new Vector<Set<Integer>>();
	private static List<Set<Integer>> neighbors_column = new Vector<Set<Integer>>();
	private static List<Set<Integer>> neighbors_block = new Vector<Set<Integer>>();
	private static List<Set<Integer>> neighbors_row_column = new Vector<Set<Integer>>();
	private static List<Set<Integer>> neighbors_row_column_block = new Vector<Set<Integer>>();
	private static List<Set<Integer>> neighbors_x = new Vector<Set<Integer>>();
	private static List<Set<Integer>> neighbors_hyper = new Vector<Set<Integer>>();
	private static List<Set<Integer>> neighbors_percent = new Vector<Set<Integer>>();
	private static List<Set<Integer>> neighbors_centerdot = new Vector<Set<Integer>>();
	private static List<Set<Integer>> neighbors_asterisk = new Vector<Set<Integer>>();
	private static List<Set<Integer>> neighbors_color = new Vector<Set<Integer>>();

	static {
		// compute rows, columns and standard block's neighbors
		for (int pos=0; pos<81; pos++) {
			// initialize entries for this position
			Set<Integer> standard_row = new TreeSet<Integer>();
			Set<Integer> standard_column = new TreeSet<Integer>();
			Set<Integer> standard_block = new TreeSet<Integer>();
			Set<Integer> standard_row_column = new TreeSet<Integer>();
			Set<Integer> standard_row_column_block = new TreeSet<Integer>();
			neighbors_row.add(standard_row);
			neighbors_column.add(standard_column);
			neighbors_block.add(standard_block);
			neighbors_row_column.add(standard_row_column);
			neighbors_row_column_block.add(standard_row_column_block);
			
			// find row and column neighbors
			int rowStart = pos/9*9;
			int columnStart = pos%9;
			for (int i=0, r=rowStart, c=columnStart; i<9; i++, r++, c+=9) {
				if (r!=pos) {
					standard_row.add(r);
					standard_row_column.add(r);
					standard_row_column_block.add(r);
				}
				if (c!=pos) {
					standard_column.add(c);
					standard_row_column.add(c);
					standard_row_column_block.add(c);
				}
			}

			// find block neighbors
			int blockStart = (pos/9/3*27) + (columnStart/3*3);
			processBlock(blockStart+0, pos, standard_block, standard_row_column_block);
			processBlock(blockStart+1, pos, standard_block, standard_row_column_block);
			processBlock(blockStart+2, pos, standard_block, standard_row_column_block);
			processBlock(blockStart+9, pos, standard_block, standard_row_column_block);
			processBlock(blockStart+10, pos, standard_block, standard_row_column_block);
			processBlock(blockStart+11, pos, standard_block, standard_row_column_block);
			processBlock(blockStart+18, pos, standard_block, standard_row_column_block);
			processBlock(blockStart+19, pos, standard_block, standard_row_column_block);
			processBlock(blockStart+20, pos, standard_block, standard_row_column_block);
		}
		((Vector<Set<Integer>>)neighbors_row).trimToSize();
		((Vector<Set<Integer>>)neighbors_column).trimToSize();
		((Vector<Set<Integer>>)neighbors_block).trimToSize();
		((Vector<Set<Integer>>)neighbors_row_column).trimToSize();
		((Vector<Set<Integer>>)neighbors_row_column_block).trimToSize();

		// compute extra regions' neighbors
		neighbors_x = computeExtraRegionNeighbors(ExtraRegionType.X);
		neighbors_hyper = computeExtraRegionNeighbors(ExtraRegionType.HYPER);
		neighbors_percent = computeExtraRegionNeighbors(ExtraRegionType.PERCENT);
		neighbors_centerdot = computeExtraRegionNeighbors(ExtraRegionType.CENTERDOT);
		neighbors_asterisk = computeExtraRegionNeighbors(ExtraRegionType.ASTERISK);
		neighbors_color = computeExtraRegionNeighbors(ExtraRegionType.COLOR);
	}
	private static void processBlock(int blockPos, int pos, Set<Integer> neighborSetAll, Set<Integer> neighborSetNoIntersection) {
		neighborSetAll.add(blockPos);
		if (pos/9!=blockPos/9 && pos%9!=blockPos%9) {
			neighborSetNoIntersection.add(blockPos);
		}
	}

    // ****************************************** Normal Sudoku (no extra regions) *******************************************

	/**
	 * In this part the neighbors for puzzles without extra regions are computed (including jigsaw puzzles)
	 */
	
	private static int[][] neighbors_rows;
	private static int[][] neighbors_columns;
	private static int[][] neighbors_blocks;		// regular blocks
	private static int[][] neighbors_normal_all;	// rows, columns, regular blocks

	public static int[][] neighbors_rows() {
		if (neighbors_rows==null) {
			neighbors_rows = convert2Array(neighbors_row);
		}
		return neighbors_rows;
	}

	public static int[][] neighbors_columns() {
		if (neighbors_columns==null) {
			neighbors_columns = convert2Array(neighbors_column);
		}
		return neighbors_columns;
	}

	public static int[][] neighbors_blocks(byte[][] blockCodes) {
		if (blockCodes!=null) {
			return computeJigsawNeighbors(blockCodes);
		}
		if (neighbors_blocks==null) {
			neighbors_blocks = convert2Array(neighbors_block);
		}
		return neighbors_blocks;
	}

	private static int[][] neighbors_jigsaw_all(byte[][] blockCodes) {
		return computeJigsawNeighbors(blockCodes, neighbors_row_column);
	}

	private static int[][] neighbors_normal_all() {
		if (neighbors_normal_all==null) {
			neighbors_normal_all = convert2Array(neighbors_row_column_block);
		}
		return neighbors_normal_all;
	}
	
	// ****************************************** X-Sudoku *******************************************

	/**
	 * In this part the neighbors for X-Sudoku puzzles are computed
	 */

	private static int[][] neighbors_normal_x;

	private synchronized static int[][] neighbors_normal_x() {
		if (neighbors_normal_x==null) {
			neighbors_normal_x = convert2Array(neighbors_row_column_block, neighbors_x);
		}
		return neighbors_normal_x;
	}
	
	private static int[][] neighbors_jigsaw_x(byte[][] blockCodes) {
		return computeJigsawNeighbors(blockCodes, neighbors_row_column, neighbors_x);
	}

	// ****************************************** Hyper-Sudoku *******************************************

	/**
	 * In this part the neighbors for Hyper-Sudoku puzzles are computed
	 */

	private static int[][] neighbors_normal_hyper;

	private synchronized static int[][] neighbors_normal_hyper() {
		if (neighbors_normal_hyper==null) {
			neighbors_normal_hyper = convert2Array(neighbors_row_column_block, neighbors_hyper);
		}
		return neighbors_normal_hyper;
	}

	private static int[][] neighbors_jigsaw_hyper(byte[][] blockCodes) {
		return computeJigsawNeighbors(blockCodes, neighbors_row_column, neighbors_hyper);
	}
	
	// ****************************************** Percent-Sudoku *******************************************

	/**
	 * In this part the neighbors for Percent-Sudoku puzzles are computed
	 */

	private static int[][] neighbors_normal_percent;

	private synchronized static int[][] neighbors_normal_percent() {
		if (neighbors_normal_percent==null) {
			neighbors_normal_percent = convert2Array(neighbors_row_column_block, neighbors_percent);
		}
		return neighbors_normal_percent;
	}

	private static int[][] neighbors_jigsaw_percent(byte[][] blockCodes) {
		return computeJigsawNeighbors(blockCodes, neighbors_row_column, neighbors_percent);
	}
	
	// ****************************************** CenterDot-Sudoku *******************************************

	/**
	 * In this part the neighbors for CenterDot-Sudoku puzzles are computed
	 */

	private static int[][] neighbors_normal_centerdot;

	private synchronized static int[][] neighbors_normal_centerdot() {
		if (neighbors_normal_centerdot==null) {
			neighbors_normal_centerdot = convert2Array(neighbors_row_column_block, neighbors_centerdot);
		}
		return neighbors_normal_centerdot;
	}

	private static int[][] neighbors_jigsaw_centerdot(byte[][] blockCodes) {
		return computeJigsawNeighbors(blockCodes, neighbors_row_column, neighbors_centerdot);
	}

	// ****************************************** Asterisk-Sudoku *******************************************

	/**
	 * In this part the neighbors for Asterisk-Sudoku puzzles are computed
	 */

	private static int[][] neighbors_normal_asterisk;

	private synchronized static int[][] neighbors_normal_asterisk() {
		if (neighbors_normal_asterisk==null) {
			neighbors_normal_asterisk = convert2Array(neighbors_row_column_block, neighbors_asterisk);
		}
		return neighbors_normal_asterisk;
	}

	private static int[][] neighbors_jigsaw_asterisk(byte[][] blockCodes) {
		return computeJigsawNeighbors(blockCodes, neighbors_row_column, neighbors_asterisk);
	}

	// ****************************************** Color-Sudoku *******************************************

	/**
	 * In this part the neighbors for Color-Sudoku puzzles are computed
	 */

	private static int[][] neighbors_normal_color;

	private synchronized static int[][] neighbors_normal_color() {
		if (neighbors_normal_color==null) {
			neighbors_normal_color = convert2Array(neighbors_row_column_block, neighbors_color);
		}
		return neighbors_normal_color;
	}

	private static int[][] neighbors_jigsaw_color(byte[][] blockCodes) {
		return computeJigsawNeighbors(blockCodes, neighbors_row_column, neighbors_color);
	}

	// ****************************************** Common Stuff Extra Regions *******************************************

	/**
	 * Compute the neighbor lists for extra regions
	 */
	private static List<Set<Integer>> computeExtraRegionNeighbors(ExtraRegionType type) {
		// initialize all extra region's neighbors
		final List<Set<Integer>> neighbors = new Vector<Set<Integer>>();
		for (int i=0; i<81; i++) {
			neighbors.add(new TreeSet<Integer>());
		}
		final List<ExtraRegion> extraRegions = ExtraRegionManager.getExtraRegions(type);
		for (ExtraRegion extraRegion:extraRegions) {
        	for (CellPosition position:extraRegion.getPositions()) {
        		final int pos = getPos(position.getX(), position.getY());
            	for (CellPosition neighborPosition:extraRegion.getPositions()) {
            		if (!position.equals(neighborPosition)) {
            			final int posNeighbor = getPos(neighborPosition.getX(), neighborPosition.getY());
            			Set<Integer> tmp = neighbors.get(pos);
                		tmp.add(posNeighbor);
            		}
            	}
        	}
		}
		return neighbors;
	}
	
	// ****************************************** Common Stuff Jigsaw Puzzles *******************************************

	/**
	 * Computes only the Jigsaw neighbors (blocks)
	 * @param blockCodes The block codes describing the Jigsaw blocks
	 */
	private static Map<String, int[][]> jigsawMapBlocks = new HashMap<String, int[][]>();
	private static int[][] computeJigsawNeighbors(byte[][] blockCodes) {
		return computeJigsawNeighbors(jigsawMapBlocks, blockCodes);
	}

	/**
	 * Computes neighbors for a Jigsaw puzzle 
	 * @param jigsawMap This map is used to cache pre-computed neighbors
	 * @param blockCodes The block codes describing the Jigsaw blocks
	 * @param neighborSets These pre-computed neighbor sets (row and column neighbors normally) will be merged with the computed jigsaw neighbors
	 */
	private static Map<String, int[][]> jigsawMap = new HashMap<String, int[][]>();
	private static int[][] computeJigsawNeighbors(byte[][] blockCodes, List<Set<Integer>>...neighborSets) {
		return computeJigsawNeighbors(jigsawMap, blockCodes, neighborSets);
	}
	
	/**
	 * Computes neighbors for a Jigsaw puzzle 
	 * @param jigsawMap This map is used to cache pre-computed neighbors
	 * @param blockCodes The block codes describing the Jigsaw blocks
	 * @param neighborSets These pre-computed neighbor sets (row and column neighbors normally) will be merged with the computed jigsaw neighbors
	 */
	private static int[][] computeJigsawNeighbors(Map<String, int[][]> jigsawMap, byte[][] blockCodes, List<Set<Integer>>...neighborSets) {
		// generate key
		StringBuffer tmp = new StringBuffer();
    	for (int y=0; y<9; y++) {
        	for (int x=0; x<9; x++) {
        		tmp.append( blockCodes[x][y] );
        	}
    	}
		String key = tmp.toString();
		// retrieve neighbors
		int[][] neighbors = jigsawMap.get(key);
		if (neighbors==null) {
			// compute neighbors and cache the last ten results in a Map
			neighbors = convert2ArrayPlus(computeBlockNeighbors(blockCodes), neighborSets);
			if (jigsawMap.size()>=10) jigsawMap.clear();
			jigsawMap.put(key, neighbors);
		}
		return neighbors;
	}
	
	/**
	 * Compute the neighbor list for a jigsaw puzzle
	 * @param blockCodes The block codes describing the Jigsaw blocks
	 */
	private static List<Set<Integer>> computeBlockNeighbors(byte[][] blockCodes) {
    	final List<Set<Integer>> neighborsList = new Vector<Set<Integer>>();
    	// compute blockCode to CellPosition mapping
		final Vector<Set<CellPosition>> blockCodes2Positions = new Vector<Set<CellPosition>>();
		for (int i=0; i<9; i++) {
			blockCodes2Positions.add(new TreeSet<CellPosition>());
		}
    	for (int y=0; y<9; y++) {
        	for (int x=0; x<9; x++) {
        		int blockCode = blockCodes[x][y];
        		Set<CellPosition> positions = blockCodes2Positions.elementAt(blockCode);
        		positions.add(new CellPosition(x, y));
        	}
    	}
    	// now fill the neighbors list
		for (int i=0; i<81; i++) {
			neighborsList.add(new TreeSet<Integer>());
		}
    	for (int y=0; y<9; y++) {
        	for (int x=0; x<9; x++) {
        		int pos = getPos(x, y);
        		Set<Integer> neighbors = neighborsList.get(pos);
        		int blockCode = blockCodes[x][y];
        		for (CellPosition position : blockCodes2Positions.elementAt(blockCode)) {
        			int posNeighbor = getPos(position.getX(), position.getY());
        			if (pos!=posNeighbor) {
        				neighbors.add(posNeighbor);
        			}
        		}
        	}
    	}
    	return neighborsList;
    }

	// ****************************************** Common Stuff *******************************************

	/**
	 * Take some neighbor lists and convert them to a neighbor array (int[][])
	 * @param positionSets The lists of neighbors to process
	 */
	private static int[][] convert2Array(List<Set<Integer>>...positionSets) {
		return convert2ArrayPlus(null, positionSets);
	}

	/**
	 * Take some neighbor lists and convert them to a neighbor array (int[][]).
	 * The plusSet is needed because a convert2ArrayPlus(List<Set<Integer>> plusSet, List<Set<Integer>>...positionSets)
	 * doesn't compile with convert2Array(List<Set<Integer>>...positionSets).
	 * @param plusSet A list of neighbors to process
	 * @param positionSets The lists of neighbors to process
	 * @return
	 */
	private static int[][] convert2ArrayPlus(List<Set<Integer>> plusSet, List<Set<Integer>>...positionSets) {
		int[][] result = new int[81][];
		Set<Integer> neighbors = new TreeSet<Integer>();
		Set<Integer> tmp = null;
		for (int pos=0; pos<81; pos++) {
			if (plusSet!=null) {
				tmp = (plusSet==null) ? null : plusSet.get(pos);
				if (tmp!=null) neighbors.addAll(tmp);
			}
			for (List<Set<Integer>> positionSet:positionSets) {
				tmp = positionSet.get(pos);
				if (tmp!=null) neighbors.addAll(tmp);
			}
			result[pos] = new int[neighbors.size()];
			int index = 0;
			for(int n:neighbors) {
				result[pos][index++] = n;
			}
			neighbors.clear();
		}
		return result;
	}

	private static int getPos(int x, int y) {
		return y*9 + x;
	}

}